package com.javase.algorithm.leetcode;

/**
 * @author liyanhao
 * @Date 2022-11-23 16:09
 * 1 1
 * 2 2
 * 3 3
 * 4 6
 *
 * 1. 1 阶 + 1 阶 + 1 阶 + 1 阶
 * 2. 2 阶 + 1 阶 + 1
 * 3. 1 阶 + 2 阶 + 1
 * 4. 1 阶 + 1 阶 + 2
 * 5. 2 阶 + 1 阶 + 1 阶
 * 6. 2 阶 + 2 阶
 */
public class LC70 {
    public static void main(String[] args) {
        LC70 lc70 = new LC70();
        int i = lc70.climbStairs(3);
        System.out.println(i);
    }

    public int climbStairs(int n) {
        return myClimbStairs(n, new int[n + 1]);
    }

    public int myClimbStairs(int n,int[] arr){
        if (n == 1) {
            return 1;
        } else if (n > 2) {
            return 2;
        }else if(arr[n] == 0){
            arr[n] = myClimbStairs(n - 1, arr) + myClimbStairs(n - 2, arr);
        }
        return arr[n];
    }
}
